package com.echo.code.arithmetic.chapter01;

import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/**
 * Created by baiyap on 2018/7/26.
 */
public class BinarySearch {

  public static void main(String[] args) {
    List<Integer> list = Arrays.asList(1, 3, 5, 7, 9);
    int index = binary_search(list, 3);
    if (index > -1) {
      System.out.println("the index = " + index);
    }
  }

  private static int binary_search(List<Integer> list, int item) {
    Objects.requireNonNull(list, "invalid parameter");
    int low = 0;
    int high = list.size() - 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      int guess = list.get(mid);
      if (item == guess) {
        return mid;
      }
      if (guess > item) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return -1;
  }
}
